package class2;

import common.ArrayUtils;

/**
 * 找到出现次数K次的数
 * 一个数组中有一种数出现 K 次，其他数都出现 M 次，找到出现了 K 次的数，K>1 K<M
 * 解题思路
 * 1.先算出所有数字，每一位的累加和
 * 2。
 */
public class Code10_FindKNumbers {
    public static void main(String[] args) {
        int[] arr = {2, 2, 2, 7, 7, 7, 7, 6, 6, 6, 6, 4, 4, 4, 4};
        int kNumbers = findKNumbers(arr, 3, 4);
        System.out.println("kNumbers = " + kNumbers);
    }

    // arr中只有一种数出现了K次，其他树都出现了 M 次
    public static int findKNumbers(int[] arr, int k, int m) {
        int[] t = new int[32];
        // 计算32位的累加和
        for (int n : arr) {
            for (int i = 0; i <= 31; i++) {
                t[i] += (n & (1 << i)) != 0 ? 1 : 0;
            }
        }
        ArrayUtils.printArr(t);

        int ans = 0;
        // 进行 取余操作，如果%==0，则是整数倍，否则为出现K的次数的数字
        for (int i = 0; i < t.length; i++) {
            if (t[i] % m != 0) {
                ans |= 1 << i;
            }
        }
        return ans;
    }
}
